#pragma once
#include <iostream>
#include <vector>
namespace CLOSE_HASH
{
    enum State
    {
        EMPTY,
        EXIST,
        DELETE
    };
    template <class K>
    struct SetKeyOfT
    {
        const K &operator()(const K &key)
        {
            return key;
        }
    };
    template <class T>
    struct HashData
    {
        T _data;
        State _state;
    };
    template <class K, class T, class KeyOfT>
    class HashTable
    {
        typedef CLOSE_HASH::HashData<T> HashData;

    public:
        bool Insert(const T &d)
        {
            KeyOfT koft;
            if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
            {
                std::vector<HashData> _newtable;
                size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                _newtable.resize(newsize);
                for (int i = 0; i < _tables.size(); i++)
                {
                    if (_tables[i]._state == EXIST)
                    {
                        size_t index = koft(_tables[i]._data) % _newtable.size();
                        while (_newtable[index]._state == EXIST)
                        {
                            ++index;
                            if (index == _newtable.size())
                            {
                                index = 0;
                            }
                        }
                        _newtable[index] = _tables[i];
                    }
                }
                _tables.swap(_newtable);
            }
            size_t index = koft(d) % _tables.size();
            while (_tables[index]._state == EXIST)
            {
                if (koft(_tables[index]._data) == koft(d))
                {
                    return false;
                }
                ++index;
                if (index == _tables.size())
                {
                    index = 0;
                }
            }
            _tables[index]._data = d;
            _tables[index]._state = EXIST;
            ++_num;
            return true;
        }
        HashData *Find(const K &key)
        {
            KeyOfT koft;
            size_t index = key % _tables.size();
            while (_tables[index]._state != EMPTY)
            {
                if (koft(_tables[index]._data) == key)
                {
                    if (_tables[index]._state == EXIST)
                    {
                        return &_tables[index];
                    }
                    else if (_tables[index]._state == DELETE)
                    {
                        return nullptr;
                    }
                }
                ++index;
                if (index == _tables.size())
                {
                    index = 0;
                }
            }
            return nullptr;
        }
        bool Erase(const K &key)
        {
            HashData *pos = Find(key);
            if (pos)
            {
                pos->_state = DELETE;
                --_num;
                return true;
            }
            else
            {
                return false;
            }
        }
        const size_t size() const
        {
            return _tables.size();
        }
        const T data(size_t n) const
        {
            return _tables[n]._data;
        }

    private:
        std::vector<HashData> _tables;
        size_t _num;
    };
    void test()
    {
        HashTable<int, int, SetKeyOfT<int>> ht;
        ht.Insert(4);
        ht.Insert(14);
        ht.Insert(24);
        ht.Insert(5);
        ht.Insert(15);
        ht.Insert(25);
        ht.Insert(6);
        ht.Insert(16);
        for (size_t i = 0; i < ht.size(); i++)
        {
            std::cout << i << " : " << ht.data(i) << std::endl;
        }
    }
}